Image information is commonly generated in a bitmap format where the bitmap comprises a plurality of "gray" level pixels (or hue concentration level pixels for color images). Pixels over a given area are defined by digital values, wherein each digital value represents a gray or hue concentration level among a number of gray or hue concentration levels within the area. Thus, in a region of 25 pixels, there are 26 levels of gray or hue concentration where each level represents an increment between black (or solid color) and white.
One standard method of converting gray or hue concentration level pixel image data into binary level pixel image data is through the use of dithering or halftoning processes. In such arrangements, over a given area having a number of gray or hue concentration level pixels therein, each pixel of an array within the area is compared to one of a set of pre-selected thresholds. This given area represents the "halftone cell". The effect of such an arrangement is that, for an area where the image is gray or some shade of a hue, some of the thresholds within the halftone cell will be exceeded, while others are not.
In the binary case, the pixels or cell elements for which thresholds are exceeded are printed as black while the remaining elements are allowed to remain white. The human eye integrates the distribution of white and black over the cell as gray. In this manner, there can be gradual transitions from different shades of gray among adjacent halftone cells.
For color applications, several halftone cells, each corresponding to a different hue, are formed for a given area. The color system superimposes the halftone cells of different hues to form the desired color of the image. Halftoning facilitates varying the concentration or intensity level of hues within the color image by varying the number of darkened pixel for halftone cells corresponding to particular hues. In this manner, the image can have transitions between neighboring colors among adjacent halftone cells. The application of halftoning to color systems is described in detail in the Postscript Reference Manual published by Adobe.
Unfortunately, in using a halftoning technique, there is often a trade-off between maximizing the number of gray or hue concentration levels and the resolution of the image; the larger each cell is (to contain more pixels), the fewer cells will fit into a given area. Fewer cells within a given area effectively decreases resolution. This gray or hue concentration level/resolution trade-off often forces product designers to choose between reproducing an image using many gray levels but in large halftone dots (resulting in coarse, grainy images) or using fine halftone dots but only a few gray or hue concentration levels (which can cause heavy banding).
To illustrate the effects of banding, FIG. 1 shows three rows 14, 16 and 18 of halftone cells, each halftone cell having twenty five pixels 22. Each of the halftone cells in halftone rows 14 and 16 have six pixels out of a possible twenty five (or 24%) darkened. This level of darkening is also referred to as a 24% halftone screen. The halftone cells in halftone row 18 have five pixels out of a possible of twenty five (or 20%) darkened. The smallest transition interval between halftone cells with this grayscaling system is 4%, or one pixel out of twenty five. As a consequence, as the image of FIG. 1 transitions from the 24% halftone screen of halftone row 16 to the 20% halftone screen of halftone row 18, there is a noticeable jump in the gray levels between adjacent regions. This is known as banding.
Some techniques have been developed to address this trade-off between gray levels and resolution in an attempt to maximize resolution while minimizing the effects of banding. Xerox Corporation developed a technique called Quad Dot. It is believed that the Quad Dot technique divides a halftone cell into four smaller cells.
The Quad Dot system attempts to distribute darkened pixels among the smaller cells. However, it is believed that the Quad Dot system sequentially adds pixels to adjacent smaller cells in a deterministic circular fashion about the center of the larger cell. This can result in a noticeable pattern within the image.